#include <stdio.h>
#include <stdlib.h>

#include "link_list_a.h"

void add_head_lla(Node** headp, void* data)
{
    Node *n = create_n(data);
    if(NULL != *headp)
        n->next = *headp;
    *headp = n;
}

void add_tail_lla(Node** headp, void* data)
{
    Node **tail = headp;
    while(NULL != *tail)
        tail = &(*tail)->next;
    *tail = create_n(data);
}

void traversal_lla(Node* head,FUNC show)
{
    while(NULL != head)
    {
        show(head->data);
        head = head->next;
    }
    printf("\n");
}

bool _del_n_lla(Node** node)
{
    Node *tmp = *node;
    *node = tmp->next;
    free(tmp);
    return true;
}

bool del_n_lla(Node** headp)
{
    if(NULL == *headp)
        return false;
    return _del_n_lla(headp);
}

bool del_tail_lla(Node** headp)
{
    if(NULL == *headp)
        return false;
    while(NULL != (*headp)->next)
        headp = &(*headp)->next;
    //free(*tail);
    //*tail = NULL;
    return _del_n_lla(headp);
}

bool del_index_lla(Node** headp, size_t index)
{
    while(index && NULL != *headp)
    {
        headp = &(*headp)->next;
        index--;
    }
    if(NULL == *headp)
        return false;
    //free(*headp);
    //*headp = (*headp)->next;
    return _del_n_lla(headp);
}

bool del_val_lla(Node** headp, void* val,CMP cmp)
{
    Node** node = query_lla(headp,val,cmp);
    if(NULL == *node)
        return false;

    return _del_n_lla(node);
}
//排重
bool del_uni_lla(Node** headp,CMP cmp)
{
    if(NULL == *headp)
        return false;
    Node *n = *headp;
    while( NULL != n && NULL != n->next )
    {
        if(!del_val_lla(&n->next,n->data,cmp))
        {
            n = n->next;
        }
    }
    return true;
}

Node** query_lla(Node** headp, void* key,CMP cmp)
{
    Node** node = headp;
    while(NULL != *node && 0 != cmp((*node)->data,key))
    {
        node = &(*node)->next;
    }
    return node;
}

void* access_last_index_lla(Node *head,size_t index)
{
    int len = 0;
    for(Node *n = head; NULL != n; n = n->next,len++);
    int cnt = len - index;
    Node *n;
    for(n = head; NULL != n && cnt > 0; n = n->next,cnt--);
    return n->data;
}

Node* reverse_ll(Node* head)
{
//    方法一,构造链表
//    Node* nHead = malloc(sizeof(Node));
//    nHead->data = head->data;
//    nHead->next = NULL;
//    head = head->next;
//    while(NULL != head)
//    {
//        Node *p = malloc(sizeof(Node));
//        p->next = nHead;
//        p->data = head->data;
//        nHead = p;
//        head = head->next;
//    }
//    return nHead;
//    方法二.调整顺序
    Node *prev = NULL;
    Node *cur = head;
    Node *next = NULL;
    while(NULL != cur)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

void sort_ll(Node* head,CMP cmp)
{
    for(Node* ip = head; NULL != ip; ip = ip->next)
    {
        int *ppi = ip->data;
        for(Node *jp = ip->next; NULL != jp; jp = jp->next)
        {
            if(0 < cmp(ip->data,jp->data)){
                ip->data = jp->data;
            }
        }
        //地址不同则值交换
        if(ppi != ip->data)
        {
            void *t = ip->data;
            ip->data = ppi;
            ppi = t;
        }
    }
}

Node* merge_ll(Node* head1, Node* head2,CMP cmp)
{
//    Node *p = head1;
//    while(NULL != head1->next){
//        head1 = head1->next;
//    }
//    head1->next = head2;
//    sort_ll(p);
//    return p;
    if(NULL == head1)
        return head2;
    if(NULL == head2)
        return head1;
//    Node *n1 = head1,*n2 = head2;
//    if(*(int*)n1->data > *(int*)n2->data)
//    {
//        Node * t = n1;
//        n1 = n2;
//        n2 = t;
//    }
//    while(NULL != n2->next && NULL != n1->next)
//    {
//        int *d1 = n1->next->data;
//        int *d2 = n2->data;
//        if(*d1 >= *d2)
//        {
//            Node *t1 = n1->next;
//            Node *t2 = n2->next;
//            n1->next = n2;
//            n2->next = t1;
//            n2 = t2;
//        }
//        else
//        {
//            n1 = n1->next;
//        }
//    }
//    n1->next = n2;
//    return head1;
    Node *min = NULL;
    if(0 > cmp(head1->data,head2->data))
    {
        min = head1;
        min->next = merge_ll(head1->next,head2,cmp);
    }
    else
    {
        min = head2;
        min->next = merge_ll(head1,head2->next,cmp);
    }
    return min;
}

bool is_circle_ll(Node* head)
{
    Node *slow = head,*fast = head;
    while(NULL != fast && NULL != fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return true;
    }
    return false;
}

Node* get_circle_ll(Node* head)
{
    Node *slow = head,*fast = head;
    while(NULL != fast && NULL != fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(fast == slow)
            break;
    }
    slow = head;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

Node* get_y_n_ll(Node* head1, Node* head2)
{
//  1.暴力遍历
    if(NULL == head1 || NULL == head2)
        return NULL;
    while(NULL != head1->next)
    {
        for(Node *n = head2; NULL != n; n = n->next){
            if(n == head1)return n;
        }
        head1 = head1->next;
    }
    return NULL;
//  2.改成栈比较
//    StackArray *s1 = createStackArray(999);
//    StackArray *s2 = createStackArray(999);
//    while(NULL != head1){
//        pushStackArray(s1,head1->data);
//        head1 = head1->next;
//    }
//    while(NULL != head2){
//        pushStackArray(s2,head2->data);
//        head2 = head2->next;
//    }
//    while(topStackArray(s1) == topStackArray(s2)){
//        popStackArray(s1);
//        popStackArray(s2);
//    }
//    return topStackArray(s1);
}
